//import java.util.ArrayList;
//import java.util.Iterator;
//
//
///** Contains the functions to run a a backtrack algorithm on a matrix
// * which represents the starting board.
// * 
// * @author romain
// * @version 0
// */
//public class BtSearch {
//	
//	private ArrayList<Node> nodes;  //records the different steps of the algorithm
//	private static Board board;
//	private Move actualMove;
//	int[] signHash;
//	PlayerNBoxes pnb;
//	
//	public BtSearch(Board b, PlayerNBoxes playerNBoxes, int[] signHash){
//		this.signHash=signHash;
//		BtSearch.board = b;
//		pnb=playerNBoxes;
//		// create the first matrix from text
//		this.nodes = new ArrayList<Node>();
//		this.nodes.add(new Node(board, playerNBoxes));
////		this.solution = "";
////		BtSearch.boxes = new ArrayList<int[]>();
//		
////		for (int i=0;i<BtSearch.board.getNumRows();i++)
////			for (int j=0;j<BtSearch.board.getNumColumns();j++)
////				if (BtSearch.board.getData(i, j)/10==1) BtSearch.boxes.add(new int[]{i,j});
////		this.initBoard.print();
//	}
//	
//	public static Board getBoard() {
//		return BtSearch.board;
//	}
//
//	public String iteration() throws CloneNotSupportedException{
//		Node actualNode = this.nodes.get(0);		
//		while (!this.nodes.isEmpty() && !BtSearch.board.isFinished(actualNode.getPlayerNBoxes())){
//			actualNode.print();
//			System.out.println("depth ="+nodes.size());
//		
//		
//			
//			this.actualMove = actualNode.findBestMove(signHash);
//			actualNode.addPerformedMove(this.actualMove);
//			System.out.println("with best move :");
//
////			actualNode.print();
//			
//			if (this.actualMove != null){
//				this.actualMove.print();
//			if (this.actualMove.valid){
//				// in this case we had a new branch
////				this.actualMove.print();
//				
//				actualNode.getPerformedMoves().add(this.actualMove);
//				this.nodes.add(new Node(BtSearch.board,
//						this.actualMove,
//						actualNode.getPlayerNBoxes(),
//						actualNode.getPerformedMoves()));
////				actualNode.print();
//				int sign=BoardSignature.getSignature(board, pnb);
//				System.out.println("the sign is : "+sign);
//				signHash[sign]+=1;
////				if(signHash[sign]==2) 
////				{   this.nodes.remove(nodes.size()-1);
////					signHash[sign]-=1;
////					continue;
////				}
////				else 
////				{	
////					System.out.println("the sign is : "+sign);
////					 actualNode.print();
////				}
//				
//			}
//			// this case means that all the possible moves have been tried
//			// so we backtrack
//			else
//				this.nodes.remove(nodes.size()-1);
//			}
//			else 
//				this.nodes.remove(nodes.size()-1);
//
//			
////			if (Node.getNb()>8) while (true);
////			System.out.println(nodes.size());
//			actualNode = this.nodes.get(nodes.size()-1);
//		}
//		if (BtSearch.board.isFinished(actualNode.getPlayerNBoxes())){
//			System.out.println("a solution has been found");
//			return manWay();
//		}
//		else return "no solution";
////		for (int i=0;i<nodes.size();i++){
////			solution += this.nodes.get(i).manWay();
////		}
//			
//	}
//	
//	/** compute the way for the man once we know the way of all the boxes.
//	 * @return solution the string to be return to the server
//	 */
//	public String manWay(){
//		Iterator<Node> itr = this.nodes.iterator();
//		String solution = "";
//		Position target, targetBox;
//		String oneWay;
//		while(itr.hasNext()) {
//			Node actualNode = itr.next();
//			//Find the target square
//			targetBox = new Position(actualNode.getPrevMove().getStart());
//			if (actualNode.getPrevMove().getDirection() == Move.MOVE_UP)
//				target = new Position(targetBox.getI()+1,targetBox.getJ());
//			else if (actualNode.getPrevMove().getDirection() == Move.MOVE_DOWN)
//				target = new Position(targetBox.getI()-1,targetBox.getJ());
//			else if (actualNode.getPrevMove().getDirection() == Move.MOVE_LEFT)
//				target = new Position(targetBox.getI(),targetBox.getJ()+1);
//			else
//				target = new Position(targetBox.getI(),targetBox.getJ()-1);
//			
//			oneWay = PathFinding.pathTo(target, actualNode.getPlayerNBoxes(), BtSearch.board);
//			
//			if (actualNode.getPrevMove().getDirection() == Move.MOVE_UP)
//				solution += oneWay+"U";
//			else if (actualNode.getPrevMove().getDirection() == Move.MOVE_DOWN)
//				solution += oneWay+"D";
//			else if (actualNode.getPrevMove().getDirection() == Move.MOVE_LEFT)
//				solution += oneWay+"L";
//			else
//				solution += oneWay+"R";
//		}
//		
//		return solution;
//	}
//	
//}
